package Hash$Set;

import java.util.*;

/**
 * 字母异位词分组
 * https://leetcode-cn.com/problems/group-anagrams/
 * 字母异位词，是指单词中字母和个数都相同，但是字母所在单词的位置不同的词
 * 对每个单词中的字母进行排序，将排序后的字符串作为 key 存入 Map 中，排序之前的字符串作为 value
 */
public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> res = new HashMap<>();
        for (String str:strs){
            //对str进行排序，生成key
            char[] s = str.toCharArray();
            Arrays.sort(s);
            String key = String.valueOf(s);
            // 判断结果字典中是否有该key，如果有，直接插入结果，如果没有，新建插入结果
            if (res.containsKey(key)){
                res.get(key).add(str);
            } else {
                res.put(key, new ArrayList<String>(){{add(str);}});
            }
        }
        //将字典转化为list
        List<List<String>> result = new ArrayList<>();
        result.addAll(res.values());
        return result;
    }
}
